package com.wfs.suanfa.leet;

import java.util.Arrays;

/**
 * 排序分析
 * 问题一：冒泡排序和插入排序的时间复杂度都是O(n)，都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎呢?
 *  1.我们前面分析冒泡排序和插入排序的时候讲到，冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。
 *  插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。
 *   2.从代码上来看冒泡需要三个赋值操作，而插入排序只需要一个，赋值时间消耗
 *
 */
public class OrderTest {
    public static void main(String[] args) {
       Integer[] arr=new Integer[]{6,5,4,3,2,1};
        //Integer[] arr=new Integer[]{1,2,3,4,5,6};
        selectSort(arr);
        for (Integer integer : arr) {
            System.out.print(integer);
        }
    }

    /**
     * 第一次循环第一个数变为最大
     */
    public static void maoPao(Integer[] arr){
        int count=0;
        for (int i=0;i<arr.length;i++){
            boolean change=false;
            int tempCount=0;
            for (int j = 0; j < arr.length-1-i; j++) {
                if (arr[j]>arr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    change=true;
                }
                tempCount++;
                count++;
            }
            System.err.println("第"+(i+1)+"次:"+tempCount);

            //if (!change) return;
            for (Integer integer : arr) {
                System.err.print(integer);
            }
            System.err.println();
        }
        System.err.println("复杂度:"+count);
    }
    /**
     * 插入排序
     */
    public static void insertSort(Integer[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int value=arr[i];
            int j=i-1;
            for (;j>=0;j--){
                if (arr[j]>value){
                    arr[j+1]=arr[j];
                }else {
                    break;
                }
            }
            arr[j+1]=value;
        }
    }
    /**
     * 选择排序
     */
    public static void selectSort(Integer[] arr) {
        for (int i = 0; i < arr.length; i++) {
           int value=arr[i];
           int temp=i;
           for (int j=i+1;j<arr.length;j++){
               if (arr[j]<value){
                   value=arr[j];
                   temp=j;
               }
           }
           arr[temp]=arr[i];
           arr[i]=value;
        }
    }
    /**
     * 归并排序
     * 代码太复杂
     */
    public static void mergeSort(Integer[] arr,int startIndex,int endIndex){
        if (startIndex>=endIndex){
            return;
        }
        int q=(startIndex+endIndex)/2;
        mergeSort(arr,startIndex,q);
        mergeSort(arr,q+1,endIndex);
        //合并

    }
    /**
     * 快排
     */
    public static void quickSort(Integer[] arr){


    }

}
